package Euler67;

import java.util.*;

public class MaximumPath {
	public static void main(String[] args) {
		
		if(args.length>0)
		{
			//Get the number of lines.
			int sum = 0;
			int numLines = 0;
			while(sum < args.length)
			{
				numLines++;
				sum += numLines;
			}
			
			//Create the pyramid.
			List<long[]> lines = new ArrayList<long[]>();
			int position = 0;
			for(int i = 0; i < numLines; i++)
			{
				long nums[] = new long[i+1];
				
				for(int j = 0; j <= i; j++)
				{
					nums[j] = Long.parseLong(args[position]);
					position++;
				}
				
				lines.add(nums);
			}
			
			System.out.println(getMaxSum(lines));
			
			//Read out values.
			/*for(int i = 0; i < lines.size(); i++)
			{
				long line[] = lines.get(i);
				
				for(int j = 0; j < line.length; j++)
				{
					System.out.print(line[j] + " ");
				}
				
				System.out.println();
			}*/
		}
		else
		{
			System.out.println("No input...");
		}
	}
	
	static long getMaxSum(List<long[]> lines)
	{
		if(lines.size() == 1)
		{
			return lines.get(0)[0];
		}
		else
		{
			//Create a new List that's a copy of the given list, minue the last 2 arrays.
			List<long[]> newLines = new ArrayList<long[]>();
			newLines.addAll(lines);
			newLines.remove(lines.size()-1);
			newLines.remove(lines.size()-2);
			
			//Sum up the last 2 line of the list and add that as the new last line.
			long line[] = new long[lines.size()-1];
			long[] line2 = lines.get(lines.size()-1);
			long[] line1 = lines.get(lines.size()-2);
			for(int i = 0; i < line.length; i++)
			{
				long a = line1[i] + line2[i];
				long b = line1[i] + line2[i+1];
				
				if(a>b)
				{
					line[i] = a;
				}
				else
				{
					line[i] = b;
				}
			}
			
			newLines.add(line);
			
			return getMaxSum(newLines);
		}
	}
}









